The present invention is related to network communications. More particularly, this specification discloses a method and an apparatus for the generation and maintenance of a wireless ad-hoc network for multicasting real-time variable-bit-rate (VBR) data among a plurality of nodes.
Wireless ad-hoc networks consist of collections of xe2x80x9cpeerxe2x80x9d mobile nodes, capable of communicating with each other, and forming a dynamically changing network with no infrastructure. In order to route packets to a destination node, each node in a wireless ad-hoc network uses other nodes in the network as relays. Therefore, it is desirable that the nodes in the network establish routing among themselves, and that the routes keep changing as the nodes move, or as the environment changes due to such factors as fading and interference. Many routing protocols have been proposed to enable effective routing in such an environment, examples of which are provided in the articles cited below. In particular, multicasting has received much attention in the Internet community. Most of the development in multicast protocols, however, has addressed wireline, fixed networks having static topologies, and are focused toward Internet applications. The majority of these Internet multicast protocols do not consider the issue of resource reservation, because the available bandwidth is generally not a problem in wireline networks. Recently, the Core-Assisted Mesh Protocol (CAMP) was proposed for effective wireless multicasting of datagram traffic. However, CAMP neither supports real-time traffic nor does it attempt to guarantee any level of quality of service (QoS). No protocol developed to date addresses multicast streaming of real-time data in a wireless ad-hoc network environment.
Most multicast protocols result in the formation of a multicast structure, which is used for transportation of multicast data. Some schemes utilize core nodes or rendezvous points, which are used to collect multicast data from sources (if there are more than one) and then to multicast the data from these nodes to the receivers. The structure built typically takes the form of a tree or a mesh.
QoS is currently a focal point of attention in both wireline and wireless networks. There are two major ideologies for delivering QoS guarantees: the integrated services model and the differentiated services model. The integrated services model attempts to provide a guaranteed notion of service, which involves reserving bandwidth from the source node to the destination node. RSVP is a signaling protocol which supports reservation of resources for multicast sessions in the Internet and is part of the integrated services specification. On the other hand, the differentiated services model is based on assigning resources to a user or edge router on a quasi-static basis. The resource is thus reserved based on what is called a service level agreement (SLA) and is then used to carry multiple classes of data. Each class of data receives a particular quality of service in terms of per-hop forwarding at each router. While, the differentiated services model is much simpler to implement than the integrated services model, it does not provide strict end-to-end quality of service guarantees in terms of bandwidth or delay.
Presently, there is a need for a multicasting method and system that is capable of supporting real-time variable bit-rate (VBR) data among the nodes of a wireless network. It is also desirable that the system be distributed, highly adaptive to variations, flexible, and scalable. Several heuristic methods have appeared in the literature, and are cited below, with the goal of developing collision-free transmission schedules. Furthermore, other approaches, also cited below, have been developed which relax the strict collision-free requirement, and in which nodes are allowed to transmit the same packet several times, where the method guarantees that at least one transmission is collision-free. Although this approach makes scheduling transparent to the network topology changes, it has the disadvantage that a packet might encounter many collisions before being able to transmit collision-free, thus significantly impacting network throughput.
A related multicast scheduler has been presented in application titled xe2x80x9cMethod and Apparatus for Multicasting Real-Time Traffic in Wireless-Ad-Hoc Networksxe2x80x9d for the provision of multicasting real-time constant bit-rate (CBR) traffic in a wireless ad-hoc network. However, real-time bursty VBR traffic presents a more difficult challenge for performing resource allocation because of its dynamically changing bandwidth requirements and its sensitivity to delay jitter. VBR traffic is both delay-sensitive and has a high degree of burstiness. For example, the peak bit-rate of video sources is several times that of their average bit rate. If bandwidth is allocated to satisfy the peak rate, the result is extremely inefficient bandwidth utilization. This kind of allocation can be sufficient for wired Internet applications, where bandwidth abounds, but the scarcity of wireless bandwidth makes this approach unacceptable for wireless ad-hoc networks. Thus, it is desirable to provide a means to reserve bandwidth adaptively in order to match the burst rate of the source dynamically. It is further desirable to re-use unused bandwidth for other applications.
1. A. Ephremides and T. V. Truong, xe2x80x9cScheduling Broadcasts in Multihop Radio Networksxe2x80x9d, IEEE Trans. Commun., vol. 38, pp. 456-460, April 1990.
2. S. Ramanathan and E. L. Lloyd, xe2x80x9cScheduling Algorithms for Multihop Radio Networksxe2x80x9d, IEEE/ACM Trans. On Networking, vol. 1, pp. 166-177, 1993.
3. C. Zhu and M. S. Corson, xe2x80x9cA Five-Phase Reservation Protocol (FPRP) for Mobile Ad-hoc Networks, in Proceedings Infocom 1998.
4. I. Chlamtac and A. Farago, xe2x80x9cMaking Transmission Schedules Immune to Topology Changes in Multi-hop Packet Radio Networksxe2x80x9d, IEEE/ACM Trans. On Networking, vol. 2, pp. 23-29, February 1994.
5. S. Chong and J. Gosh, xe2x80x9cPredictive Dynamic Bandwidth Allocation for Efficient Transport of Real-time VBR Video over ATMxe2x80x9d, IEEE J. Select. Areas Commun., vol. 13, pp. 12-23, January 1995.
6. S. Q. Li, S. Chong, C. Hwang, and X. Zhao, xe2x80x9cLink Capacity Allocation and Network Control by Filtered Input Rate in High-Speed Networksxe2x80x9d, in Proc. IEEE Globecom""90, December 1990, pp. 327-331.
7. G. J. Pottie, xe2x80x9cSystem Design Choices in Personal Communicationsxe2x80x9d, IEEE Personal Commun., pp. 50-67, October 1995.
8. D. Bertsekas and R. Gallagher, xe2x80x9cData Networksxe2x80x9d, 2nd. ed., Prentice Hall 1992.
9. C. E. Perkins and P. Bhagwat, xe2x80x9cHighly dynamic Destination-Sequenced Distance Vector routing (DSDV) for mobile computersxe2x80x9d, Proceedings of SIGCOMM""94;
10. J. Broch et al, xe2x80x9cA Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocolsxe2x80x9d, Proceedings of MOBICOM""98;
11. D. Waitzmann, S. Deering and C. Partridge, xe2x80x9cDistance vector multicast routing protocolxe2x80x9d, RFC1075 (1988);
12. A. J. Ballardie, P. F. Francis and J. Crowcroft, xe2x80x9cCore Based Treesxe2x80x9d, in Proceedings of ACM SIGCOMM, 1993;
13. J. J. Garcia-Luna-Aceves and E. L. Madruga, xe2x80x9cA multicast routing protocol for ad-hoc networksxe2x80x9d, in Proceedings INFOCOM, 1999
14. P. Ferguson and G. Hutson, xe2x80x9cQuality of service: Delivering QoS on the Internet and in Corporate Networksxe2x80x9d, John Wiley and Sons, Inc. 1998;
15. P. P. White, xe2x80x9cRSVP and integrated services on the Internet: a tutorialxe2x80x9d, IEEE Commun. Magazine, vol. 35, pp. 100-6, May 1997; and
16. http://pcl.cs.ucla.edu/projects/parsec/.
The present invention provides a method and an apparatus for transmission of variable bit-rate data through a wireless network. Specifically, the method of the present invention provides for bandwidth reservation for real-time traffic in a wireless ad-hoc network having a plurality of nodes transmitting and receiving data via a plurality of colors, with the transmitting and receiving of the data being performed periodically with a data period 2. Each of the plurality of nodes has a either a connected or disconnected connection state of either connected or disconnected. The plurality of nodes includes a communication origin node from which a data transmission occurs. Each node has a super-frame including a transmitting frame for transmitting packets and a receiving frame for receiving packets. The transmitting packets have a transmit sequence within the transmitting frame. The receiving packets have a receiving sequence within the receiving frame. A frame position F defines the position of transmitting frame within in the super-frame. Also defined are a set of transmit colors in which the node is currently transmitting, a set of colors in which the node is currently receiving, a set of usable colors, and a set of unusable colors. The nodes from which a particular node receives are identified as the parents of the particular node, with the particular node identified as the child of the parent nodes. The transmitting frame of a parent node is the receiving frame of its child node. The method comprises the following steps:
a. periodically transmitting a disconnected maintenance packet from each disconnected node, with each disconnected maintenance packet including the disconnected maintenance packet transmitting node ID, the node IDs of the parent nodes from which disconnected node seeks to receive, the frame position F of the disconnected maintenance packet transmitting node, the colors in which the disconnected maintenance packet transmitting disconnected node seeks to receive, and the receiving sequence for the disconnected maintenance packet transmitting node;
b. periodically transmitting a connected maintenance packet from each connected node, with each connected maintenance packet including the node ID of the connected maintenance packet transmitting node, the node IDs of the parent nodes from which connected node is currently receiving, the frame position of the node transmitting the connected maintenance packet, the colors in which the connected maintenance packet transmitting node receives, the receiving sequence for the maintenance packet transmitting node, a set of the usable colors in which the connected node may transmit, and a set of unusable colors in which the connected node is prohibited from transmitting;
c. receiving, at each particular node of the plurality of nodes, the maintenance packets from all nodes within a transmission range of the particular node;
d. using the maintenance packets received at each particular node to update the set of usable colors and the set of unusable colors for the particular node, where the set of usable colors for the particular node is defined as the complement of the set of unusable colors, and where the set of unusable colors of a first node N0 having transmit frame position F0 includes color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node NO receives in color c0 from a parent node Ni, where the parent node Ni is not also a parent node of Nj, and             SIR      ⁢              xe2x80x83            ⁢              (                  N          j                )              =                            G          ij                                                    ∑                              k                ≠                l                                            xe2x80x83                                      ⁢                          xe2x80x83                        ⁢                          G              kj                                +                      G                          0              ⁢              j                                           less than               γ        1              ,
xe2x80x83for a preset xcex31, such that xcex31 greater than xcex3, where:
k represents an index over all of the nodes having transmit frame positions of F0 and transmit color C0;
Gij represents the transmission power loss between the parent node Ni and node Nj;
Gkj represents the transmission power loss between a given node having an index k and transmit frame position F0, and node Nj;
G0j represents the transmission power loss between node N0 and node Nj;
xcex3 represents the threshold Signal-to-Interference Ratio (SIR) for a transmission, below which a transmission cannot take place; and
xcex31 represents a preset SIR level greater than xcex3 and chosen to decrease the probability of SIR(Nj) less than xcex3; and
e. reserving colors c0 and establishing data connections for connected and disconnected nodes Na, where a node Na can reserve color ca for receiving from a neighboring node Nc if node Na has receive frame Fc, and if node Nc can transmit in color c0 as determined in step d, and if the SIR of node Na satisfies the equation:             SIR      ⁢              xe2x80x83            ⁢              (                  N          a                )              =                            G          ca                                      ∑                          k              ≠              c                                      xe2x80x83                                ⁢                      xe2x80x83                    ⁢                      G            ka                               less than               γ        2              ,
xe2x80x83for some preset xcex32, such that xcex32 greater than xcex3, where:
k represents an index over all of the nodes having transmit frame positions of Fa and transmit color C0;
Gja represents the transmission power loss between node Nc and node Na;
Gka represents the transmission power loss between a given node having an index k and a frame position Fc, and node Na;
xcex3 represents the threshold SIR for a transmission, below which a transmission cannot take place; and
xcex32 represents a preset SIR level greater than xcex3 and chosen to decrease the probability of SIR(Nc) less than xcex3; and
f. periodically repeating steps a through e to update the ad-hoc network.
Colors are defined as channels developed from combinations selected from the group consisting of TDMA, CDMA, and FDMA schemes.
The present invention includes both the provision of a wireless ad-hoc network and operating the method on a pre-existing wireless ad-hoc network. Furthermore, the present invention includes a wireless ad-hoc network developed and maintained by the method of the present invention.
Additionally, the set of unusable colors of a first node N0 having transmit frame position F0 may be defined, as differentiated from step e above, as including color c0 if there is at least one node Nj within transmit range of node N0, having a receive frame position of F0, such that node Nj is not a child of node N0, where node N0 receives in color.